//给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：5
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= n <= 19
//
//
// Related Topics 树 二叉搜索树 数学 动态规划 二叉树 👍 2242 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function numTrees(n: number): number {

    //? dp[i] 有i个数的二叉搜索树个数
    //? dp[1] :  左0右3 dp[3]
    //? dp[2] ： 左1右2
    //? dp[3] ： 左2右1
    //? dp[4] ： 左3右0 dp[3]
    //? dp[i] = dp[i - 1] + dp[i - 2] * dp[1] ...
    const dp: number[] = [];
    dp[0] = -1; //? 表示无意义
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        //? 当前节点作为头结点和最小节点作为根节点的情况
        dp[i] = 2 * dp[i - 1];
        //? 遍历除当前节点和最小节点的每个节点当头结点 统计数量
        for (let j = 1, end = i - 1; j < end; j++) {
            dp[i] += dp[j] * dp[end - j];
        }
    }
    return dp[n];
};
//leetcode submit region end(Prohibit modification and deletion)
